// https://leetcode.cn/problems/first-missing-positive/
/*
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

-1 0
-3 -1 
-3 -2 -1 0

*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int len = nums.size();
		if(nums[len-1] <= 0 || nums[0] > 1){
			return 1;
		}
		long min = long(nums[len-1]) + 1;
		for(int i = len-1; i > 0; i--){
			if(nums[i] < 0){
				break;
			}
			if(nums[i] > 0 && i >= 1 && nums[i] - nums[i-1] > 1 && nums[i] != 1){
				min = nums[i-1]+1;
			}
			
		}
		if(min <= 0) return 1;
		return min;
    }
	
	int firstMissingPositive1(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int len = nums.size();
		if(nums[len-1] <= 0 || nums[0] > 1){
			return 1;
		}
		int i;
		long minZ = nums[len-1];
		for(i = 0; i < len; i++){
			if(nums[i] > 0){
				minZ = nums[i];
				break;
			}
		}
		if(minZ > 1) return 1;

		// minZ == 1的情况
		for(int j = i; j < len; j++){
			if(j < len-1 && nums[j+1] - nums[j] > 1){
				return nums[j]+1;
			}
		}
		return nums[len-1]+1;
    }
	
	// 二分法，效率提高50%
	int firstMissingPositive2(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int len = nums.size();
		if(nums[len-1] <= 0 || nums[0] > 1){
			return 1;
		}
		int i;
		long minZ = findMinZ(nums, len, i);
		cout << "miz:" << minZ << ",i:" << i << endl;
		if(minZ > 1) return 1;

		// minZ == 1的情况
		for(int j = i; j < len; j++){
			if(j < len-1 && nums[j+1] - nums[j] > 1){
				return nums[j]+1;
			}
		}
		return nums[len-1]+1;
    }
	
	int findMinZ(vector<int>& nums, int len, int & mid){
		if(len == 1){
			return nums[0];
		}
		int left = 0;
		int right = len - 1;
		
		while(left < right){
			mid = (left + right) / 2;
			if(nums[mid] < 0){
				left = mid + 1;
			}else if(nums[mid] == 0){
				return nums[mid+1];
			}else{
				right = mid;
			}
		}
		if(nums[mid] < 0){
			return nums[++mid];
		}
		
		return nums[mid];
	}
};

int main(){
	// vector<int> nums{1,2,0};
	vector<int> nums{-1,-2,-60,40,43};
	// vector<int> nums{3, 4, -1, 1};
	// vector<int> nums{2, 1};
	// vector<int> nums{1000, -1};
	Solution so;
	int a = so.firstMissingPositive2(nums);
	cout << a << endl;
	return 0;
}